package com.javaspeak.algorithm.graph.shortestpath.floydwarshall;

/**
 *  An example graph is shown below.  Each of the numbers in the
 *  square brackets could be a different city and the numbers in between them
 *  could be the distance between them.  In this example going from
 *  city [1] to [2] has a distance of 3.  The distance is called a weighting.
 *
 *           3        2       2
 *      [1]-----[2]------[3]-----[4]
 *       \      / \              /
 *       7\    /4  \3           / 2
 *         \  /     \          /
 *          [5]-----[6]------[7]
 *               1       2
 *
 *  The above diagram can be represented by the matrix below. In java the
 *  matrix is modelled as an array of arrays.
 *
 *  For example you can see in the matrix below that going directly from
 *  city [1] to city [5] has a distance of 7.
 *
 *  Note there are two 7s in the matrix.  The one in the top row is going
 *  from city[1] to city[5] and the one in the 5th row is going from city[5]
 *  to city[1].  In our example, the weighting is distance so the value is
 *  the same whether you are travelling between city[1] and city[5] or
 *  city[5] and city[1].
 *
 *  int[][] matrix =
 *  {
 *      { 0, 3, inf, inf, 7, inf, inf },
 *      { 3, 0, 2, inf, 4, 3, inf },
 *      { inf, 2, 0, 2, inf, inf, inf },
 *      { inf, inf, 2, 0, inf, inf, 2 },
 *      { 7, 4, inf, inf, 0, 1, inf },
 *      { inf, 3, inf, inf, 1, 0, 2 },
 *      { inf, inf, inf, 2, inf, 2, 0 }
 *   };
 *
 *   inf stands for infinity and is Integer.MAX_VALUE.
 *
 *   In the line, { 0, 3, inf, inf, 7, inf, inf } the first inf, means that it
 *   is not possible to go directly from [1] to [3].
 *
 *   After calling fillWeight( int[][]matrix ) matrix looks like:
 *
 *   int[][] expectedData =
 *   {
 *       { 0, 3, 5, 7, 7, 6, 8 },
 *       { 3, 0, 2, 4, 4, 3, 5 },
 *       { 5, 2, 0, 2, 6, 5, 4 },
 *       { 7, 4, 2, 0, 5, 4, 2 },
 *       { 7, 4, 6, 5, 0, 1, 3 },
 *       { 6, 3, 5, 4, 1, 0, 2 },
 *       { 8, 5, 4, 2, 3, 2, 0 }
 *   };
 *
 *  Notice that the infs have been replaced with values. The values are worked
 *  out by going via other nodes.
 *
 *  Note that in some scenarios the weighting is not the same going from [1]
 *  to [2] as going from [2] to [1] and could even be negative in one direction.
 *  For example if the weighting was for the energy required for an electric
 *  bike and the locations were at different heights and the bike had a
 *  dynamo then when it is rolling down a hill it could generate electricity
 *  and when it was going in the opposite direction it would require electricty
 *  from the battery to go up hill.  Where there is a hill between 2 locations
 *  the energy weighting would be negative in one direction and postive in the
 *  other direction.
 *
 *  @author John Dickerson
 */
public class FloydWarshallMatrix {

    /**
     * This method works out the minimum distance between every point (going
     * via other points if necessary).
     * <p>
     * The initial matrix passed in to this method shows the weightings going
     * directly from one point to another point.  If it is not possible to go
     * directly from say point [1] to point[4] then the matrix will show
     * "inf" for that value. "inf" is Integer.MAX_VALUE and is a marker that
     * is telling us that it is not possible to go directly between the points
     * without going via another point.
     * <p>
     * This method will update the value of going from a given point to another
     * point with values created by going via other points.  It will only update
     * a value if it can be made smaller.  Sometimes going via other points
     * results in a smaller value.  Often one can only get from one point to
     * another one by going via other points.
     * <p>
     * After running this method you will find that the "infs" are replaced with
     * values if it is possible to go from one point to another one via other
     * points.
     *
     * @param matrix The matrix of data representing the graph.
     */
    public static void fillWeight( int[][]matrix ){

        for ( int b=0; b<matrix.length; b++ ){

            for ( int a=0; a<matrix.length; a++ ){

                for ( int c=0; c<matrix.length; c++ ){

                    if ( matrix[ a ][ b ] != Integer.MAX_VALUE &&  
                            matrix[ b ][ c ] != Integer.MAX_VALUE &&
                                    matrix[ a ][ b ] + matrix[ b ][ c ] <  
                                        matrix[ a ][ c ] ){
                        
                        matrix[ a ][ c ] =  matrix[ a ][ b ] + matrix[ b ][ c ];
                    }
                }
            }
        }
    }


    public static int getShortestPath( int[][]matrix, int x, int y ){

        return matrix[ x ][ y ];
    }
}
